package org.xqh.study.leetcode.algorithm.graph.bfs;

import java.util.*;

/**
 * @ClassName SlidingPuzzle
 * @Description https://leetcode-cn.com/problems/sliding-puzzle/
 * 滑动谜题
 * @Author xuqianghui
 * @Date 2021/3/2 15:50
 * @Version 1.0
 */
public class SlidingPuzzle {

    public static void main(String[] args) {
        int[][] arr = {{4, 1, 2},{5, 0, 3}};
//        System.out.println(Arrays.deepToString(arr));
        System.out.println(slidingPuzzle(arr));
    }

    public static int slidingPuzzle(int[][] board) {
        int rows = board.length; int cols = board[0].length;
        Queue<BFSNode> queue = new ArrayDeque<>();
        //寻找 0 所在位置
        int ir = 0, ic = 0;
        f: for(int i = 0;i < rows; i++){
            for(int j = 0;j < cols; j ++){
                if(board[i][j] == 0){
                    ir = i;
                    ic = j;
                    break f;
                }
            }
        }

        int[][] directions = {{-1, 0},{1, 0},{0, -1},{0, 1}};//上下左右 四个移动方向
        BFSNode first = new BFSNode(board, ir, ic, 00);
        queue.offer(first);
        Set<String> seen = new HashSet<>();
        seen.add(first.boardString);
        //目标 结果
        String target = Arrays.deepToString(new int[][]{{1, 2, 3}, {4, 5, 0}});
        while (!queue.isEmpty()){
            BFSNode cur = queue.remove();
            if(target.equals(cur.boardString)){
                return cur.depth;
            }
            for(int[] di:directions){
                int dr = di[0] + cur.nr;
                int dc = di[1] + cur.nc;
                //判断 边界
                if(dr < 0 || dc < 0 || dr >= rows || dc >= cols){
                    continue;
                }
                int[][] newBoard = new int[rows][cols];
                //替换 0 和 对应位置的元素
                for(int i = 0; i < rows; i++){
                    System.arraycopy(cur.board[i], 0, newBoard[i], 0, cols);
                }
                int tmp = newBoard[dr][dc];
                newBoard[cur.nr][cur.nc] = tmp;
                newBoard[dr][dc] = 0;
                BFSNode nb = new BFSNode(newBoard, dr, dc, cur.depth + 1);
                if(seen.contains(nb.boardString)){
                    continue;
                }
                queue.offer(nb);
                seen.add(nb.boardString);
            }
        }
        return -1;
    }

    public static class BFSNode{
         int[][] board;
         String boardString;
         int nr;//行
         int nc;//列
         int depth;//当前节点深度

        public BFSNode(int[][] board, int nr, int nc, int depth){
            this.board = board;
            this.nr = nr;
            this.nc  = nc;
            this.depth = depth;
            this.boardString = Arrays.deepToString(board);
        }
    }
}
